A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, such as an Ethernet network, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
The packets are communicated according to a communication protocol that defines the format of the packet. A typical packet, for example, includes a header carrying source and destination information, as well as a payload that carries the actual data. The de facto standard for communication in conventional packet-based networks, including the Internet, is the Transmission Control Protocol/Internet Protocol (TCP/IP).
A user, such as a system administrator, often makes use of a network analysis device to monitor network traffic and debug network problems. For example, the user may make use of a network analyzer, which is a stand-alone device that captures data from a network and displays the data to the user. Alternatively, other network devices, such as routers, gateways, and the like, may incorporate traffic flow analysis functionality.
The network analysis devices typically monitor and collect packets having network information that matches criteria specified by the user. For example, the user may specify a source and destination Internet Protocol (IP) addresses, source and destination port numbers, protocol type, type of service (ToS) and input interface information. The network analysis devices typically collect packets matching the specified criteria, and construct flow analysis diagrams. The user may then view the information collected for network traffic flowing between devices on the network. The information may be used for network planning, traffic engineering, network monitoring, usage-based billing and the like.
Some systems forward a copy of the network traffic to a network analysis device for batch processing. Other network devices attempt to analyze the data locally and resolve user queries in “real time.” One challenge associated with this latter approach is that the data being collected and reported, i.e., traffic flow statistics, is continuously being updated. In other words, the statistics for the various packet flows must be continuously updated as traffic continues to flows through the network. Consequently, it is often difficult to analyze the data at any particular point in time in order to respond to a user query, such as a request for the largest packet flows through the network. This task is further compounded by the immense volume of traffic that may be flowing through the network. To further complicate the process, multiple queries may be received concurrently from different users.